package com.dh.leetcode.four;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedHashMap;

/**
 * @ClassName: _423_reconstruct_original_digits_from_english
 * @Description: 423. 从英文中重建数字
 * 给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "owoztneoer"
 * 输出："012"
 * 示例 2：
 * <p>
 * 输入：s = "fviefuro"
 * 输出："45"
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 105
 * s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一
 * s 保证是一个符合题目要求的字符串
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reconstruct-original-digits-from-english
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: shouzimu
 * @Date: 2021/11/24 8:26
 */
public class _423_reconstruct_original_digits_from_english {

    //根据唯一性程度构建顺序
    /**
     * z只存在于0
     * w只存在于2
     * x只在6中出现
     * g存在于8
     * 8中去除h后 h只在3中出现
     * 6中去除s后 s只在7中出现
     * 7中去除v后 v只在5中出现
     * 5中去除i后 f只在4中出现
     * 5、6、8中去除i后 i只在9中出现
     * 9、7中去除n 得 1
     * <p>
     * 顺序 0-2-6-8-3-7-5-4-9-1
     */
    static LinkedHashMap<String, Integer> map = new LinkedHashMap<>();

    static {
        map.put("zero", 0);
        map.put("two", 2);
        map.put("six", 6);
        map.put("eight", 8);
        map.put("three", 3);
        map.put("seven", 7);
        map.put("five", 5);
        map.put("for", 4);
        map.put("nine", 9);
        map.put("one", 1);
    }


    public String originalDigits(String s) {
        int[] bucket = new int[26];
        for (int i = 0; i < s.length(); i++) {
            bucket[s.charAt(i) - 'a']++;
        }
        int[] array = new int[10];
        array[0] = bucket['z' - 'a'];
        array[2] = bucket['w' - 'a'];
        array[6] = bucket['x' - 'a'];
        array[8] = bucket['g' - 'a'];
        array[3] = bucket['h' - 'a'] - array[8];
        array[7] = bucket['s' - 'a'] - array[6];
        array[5] = bucket['v' - 'a'] - array[7];
        array[4] = bucket['f' - 'a'] - array[5];
        array[9] = bucket['i' - 'a'] - array[5] - array[6] - array[8];
        array[1] = bucket['n' - 'a'] - 2 * array[9] - array[7];
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i]; j++) {
                builder.append(i);
            }
        }
        return builder.toString();
    }

    /**
     * 第一版还是智商不够，根据词频复杂程度优先处理对应的数值
     *
     * @param s
     * @return
     */
    public String originalDigits2(String s) {
        int[] bucket = new int[26];
        for (int i = 0; i < s.length(); i++) {
            bucket[s.charAt(i) - 'a']++;
        }
        StringBuilder builder = new StringBuilder();
        for (String s1 : map.keySet()) {
            while (true) {
                int[] copyBucket = Arrays.copyOf(bucket, bucket.length);
                int i = getString(bucket, s1);
                if (i > -1) {
                    builder.append(i);
                } else {
                    bucket = copyBucket;
                    break;
                }
            }

        }
        char[] array = builder.toString().toCharArray();
        Arrays.sort(array);
        return new String(array);
    }

    public int getString(int[] bucket, String str) {
        boolean full = true;
        for (int i = 0; i < str.length(); i++) {
            if (bucket[str.charAt(i) - 'a']-- < 1) {
                full = false;
                break;
            }
        }
        if (full) {
            return map.get(str);
        } else {
            return -1;
        }
    }

    @Test
    public void originalDigitsTest() {
        Assert.assertEquals("0123456789", originalDigits("zeroonetwothreefourfivesixseveneightnine"));
        Assert.assertEquals("012", originalDigits("owoztneoer"));
        Assert.assertEquals("45", originalDigits("fviefuro"));
        Assert.assertEquals("0112", originalDigits("owoztneoerone"));

    }
}
